package com.fengdi.everyday.middle;

import java.util.*;

/**
 * @Description 3607: 电网维护
 * @Date 15:47
 */

public class ProcessQueries {
    private static class UnionSet {
        private final int[] parent;
        private final int[] rank;

        //  初识化并查集
        UnionSet(int n) {
            this.parent = new int[n + 1];
            this.parent[0] = -1;
            for(int i = 1; i < n + 1; i++) {
                this.parent[i] = i;
            }

            this.rank = new int[n + 1];
            Arrays.fill(this.rank, 0);
            this.rank[0] = -1;
        }

        public int find(int x) {
            if(this.parent[x] != x) {
                this.parent[x] = this.find(this.parent[x]);
            }
            return this.parent[x];
        }

        public void union(int x, int y) {
            int root_x = this.find(x);
            int root_y = this.find(y);

            if(root_x == root_y) return; // 属于同一集合

            if(this.rank[root_x] < this.rank[root_y]) {
                this.parent[root_x] = root_y;
            }else if(this.rank[root_x] > this.rank[root_y]) {
                this.parent[root_y] = root_x;
            }else {
                this.parent[root_y] = root_x;
                this.rank[root_x] += 1;
            }
        }
    }

    private UnionSet set;

    public int[] processQueries(int c, int[][] connections, int[][] queries) {
        ArrayList<Integer> ans = new ArrayList<>();

        boolean[] status = new boolean[c + 1];
        Arrays.fill(status, true);

        int[] offlineCounts = new int[c + 1];
        // 1. 创建并查集
        this.set = new UnionSet(c);

        // 2. 组网
        this.createNetwork(connections);
        Map<Integer, TreeSet<Integer>> gridOnline = new HashMap<>();
        for(int i = 1; i <= c; i++) {
            int root = this.set.find(i);
            gridOnline.computeIfAbsent(root, k -> new TreeSet<>()).add(i);
        }

        // 3. 执行操作
        for(int[] query : queries) {
            int operationType = query[0];
            int operationID = query[1];

            switch(operationType) {
                case 1: { // 浏览电站
                    if(status[operationID]) {
                        ans.add(operationID);
                    }else {
                        int root = this.set.find(operationID);
                        TreeSet<Integer> onlineSet = gridOnline.get(root);
                        ans.add(onlineSet.isEmpty() ? -1 : onlineSet.first());
                    }
                }break;
                case 2: { // 关闭电站
                    if(status[operationID]) {
                        status[operationID] = false;
                        int root = this.set.find(operationID);
                        gridOnline.get(root).remove(operationID);
                    }
                }break;
            }
        }

        return ans.stream().mapToInt(Integer::intValue).toArray();
    }

    private void createNetwork(int[][] connections) {
        for(int[] connection : connections) {
            this.set.union(connection[0], connection[1]);
        }
    }
}
